1. Field of the Invention
The present invention relates generally to coordination amongst execution sequences in a multiprocessor computer, and more particularly, to structures and techniques for facilitating non-blocking access to concurrent shared objects.
2. Description of the Related Art
It is well known that availability of automatic dynamic memory management facilities, often referred to as garbage collection (GC), can simplify the design of sequential implementations of data structures. Furthermore, availability of garbage collection facilities can simplify the handling of various synchronization issues in the design of concurrent data structures.
For example, concurrent data structure implementations for an execution environment that provides garbage collection can benefit from a free solution to the so-called ABA problem. The ABA problem arises when a data system fails to detect that a value changes (e.g., from A to B) and then changes back to its original value (i.e., A). For example, if a compare-and-swap-type operation (e.g., a CAS or DCAS operation) is about to operate on a pointer and the object to which it points is freed and then reallocated, then it is possible for the CAS or DCAS to succeed even though it should fail. In a proper implementation, this possibility should be prevented by ensuring that an object is not freed while an execution thread has pointers to it. Garbage collector implementations typically ensure such behavior, e.g., by stopping a thread and inspecting its registers and stack for pointers. However, in the absence of a garbage collector, responsibility for handling the ABA problem generally falls to the concurrent data structure implementation itself.
While use of a garbage-collected execution environment is possible in some situations, such an environment is not always available. For example, many common programming and execution environments do not support garbage collection. Second, even those environments that do support garbage collection typically employ excessive synchronization, such as locking and/or stop-the-world mechanisms, which impair scalability and may be impractical for certain applications. Finally, concurrent shared object implementations that depend on the existence of a garbage collection facility are generally not suitable for use in the implementation of the garbage collector itself.
In view of the above, structures and techniques are desired that would allow programmers to exploit the advantages of a garbage collected execution environment in the design of data structure implementations despite the absence of a garbage collection facility.